The present invention relates generally to electronic circuits and more particularly to adder circuits for use in semiconductor integrated circuits and other electronic devices.
As a result of ever-shrinking very large scale integration (VLSI) process geometries, it has become necessary to reexamine the tradeoffs that have been made in the existing design and implementation of computer arithmetic algorithms. Algorithms utilizing the so-called carry lookahead technique, as described in A. Weinberger and J. L. Smith, xe2x80x9cA One-Microsecond Adder Using One-Megacycle Circuitry,xe2x80x9d IRE Trans. on Electronic Computers, pp. 65-73, June 1956, speed up the addition process by unrolling a recursive carry equation. Both transistor count and interconnection complexity have typically limited the maximum unrolling to 4 bits. Larger adders have been built as block carry-lookahead adders, where the lookahead operation occurs within small blocks, as described in T.-F. Ngai et al., xe2x80x9cRegular, Area-Time Efficient Carry-Lookahead Adders,xe2x80x9d Journal of Parallel and Distributed Computing, Vol. 3, pp. 92-105, 1986.
The recursive carry computation can also be reduced to a prefix computation, as described in, e.g., P. M. Kogge and H. S. Stone, xe2x80x9cA Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations,xe2x80x9d IEEE Trans. on Computers, Vol. C-22, No.8, pp. 786-793, August 1973. As described in R. P. Brent and H. T. Kung, xe2x80x9cA Regular Layout for Parallel Adders,xe2x80x9d IEEE Trans. on Computers, Vol. C-31, No. 3, pp. 260-264, March 1982, a prefix tree can be used to compute the carry at the most-significant bit position, and an additional tree superimposed on the prefix tree can be used to compute the intermediate carries. Faster computation of all the carries can be achieved by using a separate prefix tree for each bit position, as described in D. Dozza et al., xe2x80x9cA 3.5 NS, 64 Bit, Carry-Lookahead Adder,xe2x80x9d in Proc. Intl. Symp. Circuits and Systems, pp. 297-300, 1996.
A problem associated with the above-noted full prefix tree adders, which are also known as Kogge-Stone adders, is the additional delay introduced as a result of exponentially growing interconnection complexity. Existing architecture tradeoffs have emphasized reduction of interconnection complexity at the expense of higher gate fanouts. Interconnection complexity can also be reduced by using hybrid carry lookahead/carry select architectures which eliminate the need to implement a full prefix tree for each bit position. The use of low resistance and low capacitance materials can reduce the negative effects of architectures that depend on large amounts of interconnect, as described in J. Silberman et al., xe2x80x9cA 1.0 GHz Single-Issue 64b PowerPC Integer Processor,xe2x80x9d IEEE Intl. Solid-State Circuits Conf., pp. 230-231, February 1998. Furthermore, with additional levels of interconnect, the area overhead required to implement such adders is alleviated through the use of extensive xe2x80x9cover-the-cellxe2x80x9d routing, which removes the routing channels and further minimizes the interconnect capacitance.
The operation of a conventional prefix tree adder will now be described in greater detail. In a general n-bit prefix tree adder, the addition of two numbers A and B,       A    =                            -                      a                          n              -              1                                      ⁢                  2                      n            -            1                              +                        ∑                      j            =            0                                n            -            2                          ⁢                  xe2x80x83                ⁢                              a            j                    ⁢                      2            j                                    B    =                            -                      b                          n              -              1                                      ⁢                  2                      n            -            1                              +                        ∑                      j            =            0                                n            -            2                          ⁢                  xe2x80x83                ⁢                              b            j                    ⁢                      2            j                              
represented in two""s complement binary form, can be accomplished by computing:                                                         g              j                        =                                          a                j                            ⁢                              b                j                                                                                                    p              j                        =                                          a                j                            ⊕                              b                j                                                                                                    c              j                        =                                          g                j                            +                                                p                  j                                ⁢                                  c                                      j                    -                    1                                                                                                                                      s              j                        =                                          p                j                            ⊕                              c                                  j                  -                  1                                                                          }    ⁢      xe2x80x83    ⁢      ∀                  j        ⁢                  xe2x80x83                ⁢        0            ≤      j       less than       n      
where cxe2x88x921 is the primary carry-input. The signals designated gj, pj and cj are referred to herein as generate, propagate and carry signals, respectively. The resulting sum of A and B is   S  =                    -                  s                      n            -            1                              ⁢              2                  n          -          1                      +                  ∑                  j          =          0                          n          -          2                    ⁢              xe2x80x83            ⁢                        s          j                ⁢                              2            j                    .                    
An overflow occurs, and the resulting sum is invalid, if
cnxe2x88x921⊕cnxe2x88x922=1.
The above-cited Dozza et al. reference defines (Gjj, Pjj)=(gj, pj), and
(Gij,Pij)=(gj,pj)o(gjxe2x88x921,pjxe2x88x921)o . . . o(gi,pi) if j greater than i,
where o is the fundamental carry operator described in the above-cited Brent and Kung reference and defined as
(gj,pj)o(gi,pi)=((gj+pjgi)pjpi).
The fundamental carry operator o is both associative and idempotent. At each bit position, the carry is given by
cj=G0j+P0jcxe2x88x921
where cxe2x88x921 is the primary carry input. If there is no primary carry input, then cj is simply G0j.
An additional speedup in the above-described conventional prefix tree adder can be achieved by using transmit signals tj instead of propagate signals pj to compute the carries for each bit position. The final sum computation still requires the propagate signals pj to be generated from the primary inputs. However, the propagate signal pj can be computed as pj={overscore (g)}jtj, in order to reduce the load on the primary inputs and to eliminate the need for an XOR gate for generating the propagate signal pj.
The addition operation in this case is defined as                                                         g              j                        =                                          a                j                            ⁢                              b                j                                                                                                    t              j                        =                                          a                j                            +                              b                j                                                                                                    p              j                        =                                                            a                  j                                ⊕                                  b                  j                                            =                                                                    g                    _                                    j                                ⁢                                  t                  j                                                                                                                    c              j                        =                                          g                j                            +                                                t                  j                                ⁢                                  c                                      j                    -                    1                                                                                                                                      s              j                        =                                          p                j                            ⊕                              c                                  j                  -                  1                                                                          }    ⁢      xe2x80x83    ⁢      ∀                  j        ⁢                  xe2x80x83                ⁢        0            ≤      j       less than       n      
where (Gjj, Tjj) (gj, tj), and
(Gjj,Tjj)=(gj,tj)o(gjxe2x88x921,tjxe2x88x921)o . . . o(gi, ti) if j greater than i,
where o is the fundamental carry operator. The computation of (G0j, T0j) ∀j follows the same methodology as above for (G0j, P0j). The carry cj for each bit position is then given by
cj=G0j+T0jcxe2x88x921
where cxe2x88x921 is the primary carry input. If there is no primary carry input, then cj is simply G0j.
The tj signals can be computed faster than the pj signals since an OR gate is typically faster than an XOR gate. Hence, the carry computation through the prefix trees can start slightly earlier if the transmit signals are used. Since the sum generation step still uses the propagate signals, the load on the transmit signals in this architecture is smaller than the load on the propagate signals in the architecture which uses the pj signals to compute the carries. However, the load on the input signals is now higher since both transmit and propagate signals need to be generated.
Improved prefix tree adders which provide significant reductions in logic depth, delay and circuit area relative to the above-described conventional prefix tree adders are disclosed in the above-cited U.S. patent application Ser. No. 09/291,677. Although these improved prefix tree adders provide substantial advantages over conventional prefix tree adders, a need nonetheless remains for further improvements, particularly in terms of the computational delay parameter.
The invention provides an improved prefix tree adder in which a significant delay reduction is achieved by implementing sum computation logic circuitry in a final stage of the adder so as to exploit the differing delays with which group-generate (G), group-transmit (T) and intermediate carries (c) are generated. Previous adder designs have not exploited these final-stage delay differences to reduce the overall computation delay of the adder.
In accordance with one aspect of the present invention, an n-bit prefix tree adder includes n prefix trees, each associated with a bit position of the adder and including a number of computation stages. The computation stages for each of the bit positions include a sum computation stage implemented in logic circuitry. For at least a subset of the bit positions, the corresponding sum computation logic circuitry computes a sum based at least in part on group-generate, group-transmit and intermediate carry signals. Advantageously, the sum computation logic circuitry is configured to exploit differences in delay associated with generation of the group-generate, group-transmit and intermediate carry signals, so as to reduce the total computational delay of the adder.
In accordance with another aspect of the invention, additional delay reduction may be achieved by configuring the sum computation stages of the adder in accordance with a left-to-right routing of most-significant group-generate and group-transmit signals, such that the most-significant half of the sum bits are generated in the same prefix trees in which the least-significant half of the sum bits are generated.